/*
本题要求一种搭配方式使得美观程度最大，可以考虑使用 dp

每次考虑第 i 朵花应该放在哪个花瓶中，由此就能得到我们的状态表示。

设 f[i][j] 表示放了 i 朵花，且第 i 朵花放在第 j 个花瓶中能获得的美观程度最大值。

放第 i 朵花的状态需要从放第 i - 1 朵花的状态转移过来，且第 i - 1 朵花只能放在第 i 朵花左边。

f[i][j] = max{ f[i - 1][1], f[i - 1][2], ..., f[i - 1][j - 1] } + w[i][j]

最开始第一朵花可以放在任意一个位置，因此起始状态为 f[1][j] = w[1][j] (1 <= j <= V)

最终目标是放完 F 朵花，但是第 F 朵花放在哪需要枚举一下，因此结束状态为 max{ f[F][j] } (1 <= j <= V)

本题还需要输出方案，我们可以根据状态转移方程从结束状态反着推到起始状态，这样每一步是把哪朵花
放到哪个花瓶都能清楚知道，但是本题要求从前往后输出每朵花放在哪个花瓶，但是我们倒推方案是从后
往前推的，这样我们还要将方案记录下来再倒着输出有点麻烦。

我们可以刚开始就反着放花，这样起点状态就是 f[n][j]，而结束状态就是 f[1][j]，同样的将状态转移方程稍作变化，
本来是从 i - 1 转移到 i，现在改成从 i + 1 转移到 i，区别在于 i - 1 必须放在 i 的左边，而 i + 1 必须放在 i
的右边。

新转移方程:f[i][j] = max{ f[i + 1][j + 1], f[i + 1][j + 2], ..., f[i + 1][V] } + w[i][j]

这样我们再去倒推方案时，就能从前往后输出每朵花放在哪个花瓶中。
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m;
int a[N][N]; //表示每朵花放在每个花瓶中的美观程度
int f[N][N]; //设f[i][j] 表示放了 i 朵花，且第 i 朵花放在第 j 个花瓶中能获得的美观程度最大值

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    //初始化
    memset(f, -0x3f, sizeof f);
    for(int i = 1; i <= m; i++) f[n][i] = a[n][i];

    //dp
    for(int i = n - 1; i >= 1; i--)
        for(int j = 1; j <= m; j++)
            for(int k = j + 1; k <= m; k++)
                f[i][j] = max(f[i][j], f[i + 1][k] + a[i][j]);

    //找出结束状态，即最后一朵花摆放的位置
    int j = 1;
    for(int k = 1; k <= m; k++)
        if(f[1][k] > f[1][j])
            j = k;

    printf("%d\n", f[1][j]);

    //倒推方案
    int i = 1;
    while(i <= n)
    {
        printf("%d ", j);
        for(int k = j + 1; k <= m; k++) //每个花尽量往前放，保证方案字典序最小
            if(f[i][j] == f[i + 1][k] + a[i][j])
            {
                j = k; //第一个能转移的花瓶就是字典序最小的方案
                break; //当前花找到对应的位置，直接跳出循环
            }
        i++; //继续找下一朵花的位置
    }

    return 0;
}

